In a collection of computing devices, a data item may be multiply replicated to create a number of copies of the item on the different computing devices and/or possibly within a single device. An item may be any stored data object, such as for example contact or calendar information, stored pictures or music files, software application programs, files or routines, etc. The collection of computing devices may for example be a desktop computer, a remote central server, a personal digital assistant (PDA), a cellular telephone, etc. The group of all such items and replicas where the items are stored may be referred to as a distributed collection.
In many cases, a user would like all of their various data storing devices to have the latest updated information without having to manually input the same changes into each device data store. Replication, or synchronization, of data is one process used to ensure that each data store has the same information. Synchronization protocols are the means by which devices exchange created and updated versions of items in order to bring themselves into a mutually consistent state. The periodicity of the sync may vary greatly. Networked devices may sync with each other frequently, such as once every minute, hour, day, etc. Alternatively, devices may sync infrequently, such as for example where a portable computing device is remote and disconnected from a network for a longer period of time. Whether the synchronization is frequent or infrequent, the distributed collection is said to be weakly-consistent in that, in any given instant, devices may have differing views of the collection of items because items updated at one device may not yet be known to other devices.
As an example, a user may maintain an electronic address book or a set of email messages in a variety of different devices or locations. The user may maintain the address book or email addresses, for example, on a desktop computer, on their laptop computer, on a personal digital assistant (PDA) and/or mobile phone. The user may modify the contact information or send/receive email addresses using applications associated with each location. Regardless of where or how a change is made, one goal of replication is to ensure that a change made on a particular device or in a particular location is ultimately reflected in the data stores of the other devices and in the other locations.
FIG. 1 illustrates a weakly-consistent distributed collection, including multiple replicas A-F. Each replica A-F may be a computing device including a data store and associated processor. However, as is known, a single computing device may include several replicas, and a single replica may be implemented using more than one computing device. In the example of FIG. 1, the replicas may include a desktop computer A, a pair of laptop computers B and C, a cellular telephone D, a personal digital assistant (PDA) E and a digital camera F. The number and type of replicas is by way of example and may be more, less and/or different than shown. FIG. 1 further shows communication links 22 (represented by dashed lines) between the various replicas to establish a peer-to-peer network. It may often be the case that not all replicas are linked to all other replicas. For example, laptop B is linked to desktop A, laptop C, cellular phone D and PDA E, but not digital camera F. Consequently, laptop B can sync with digital camera F only through one or more intermediate sync steps involving replicas C or E. The illustrated communication links can be wired and/or wireless links. The configuration of communication links between replicas is called the “synchronization topology”. Two replicas that communicate periodically to synchronize their shared data are called sync “partners”.
Synchronization between replicas may be described as a sharing of knowledge between replicas. A common knowledge sharing scheme involves tracking, within each replica, changes that have occurred to one or more items subsequent to a previous replication. One such tracking scheme makes use of version vectors, which consist of list of version numbers, one per replica, where each version number is an increasing count of updates made to an item by a replica. During synchronization, one replica sends version vectors for all of its stored items to another replica, which uses these received version vectors to determine which updated items it is missing. Comparing the version vectors of two copies of an item tells whether one copy is more up-to-date (every version number in the up-to-date copy is greater than or equal to the corresponding version number in the other copy) or whether the two copies conflict (the version vectors are incomparable). The replica may then update its copy of the item if required or make efforts to resolve the detected conflict.
Although version vectors enable replicas to synchronize correctly, they introduce overhead. The version vector of each item may take O(N) space in an N replica replication system, thus requiring O(M*N) space across an M item collection. This space requirement could be substantial if the number of items is large and could approach the size of the items themselves if items are small. Similarly, exchanging version vectors during synchronization consumes bandwidth. Even if two replicas have fully consistent data stores, they still need to send a complete list of version vectors whenever they periodically perform synchronization.
Another knowledge sharing scheme, implemented for example in the WINFS data storage and management system from Microsoft Corp., makes use of knowledge vectors. Unlike version vectors, knowledge vectors are associated with the replicas rather than the items. Each replica keeps a count of the updates it generates, and the knowledge vector of a replica consists of the version number of the latest update it learned from every other replica. In addition, items at a replica have a single version number indicating the latest update applied to it. Replicas exchange knowledge vectors during synchronization, determine and exchange the missing updates, and change their knowledge vector to reflect the newly-learned knowledge (each number is set to the maximum of the corresponding numbers in the two knowledge vectors of the synchronizing replicas).
An example of knowledge sharing between a pair of replicas using knowledge vectors is illustrated with respect to prior art FIGS. 2 and 3. In the example of FIGS. 2 and 3, replica A is synching with replica B. Replica A has a data store 24 including a knowledge vector, KA, and a set of replicated items. The knowledge vector in replica A includes one or more pairs of replica IDs together with update counters, which together represent what knowledge replica A has about changes that have occurred to items in the collection. For example, knowledge vector KA may have the components:KA=A5B3C7.This means that replica A has knowledge including changes up to the 5th change in replica A, the 3rd change in replica B, and the 7th change in replica C.
Each of the changes indicated in the knowledge vector may be represented in the set of replicated items. For example, assume four items in the collection, identified by unique identifiers i, j, l and m. The set of items stored in data store 24 at Replica A may look as follows:
TABLE 1ItemUnique IDVersionDataiA2. . .jC7. . .lA5. . .mB3. . .The data store thus indicates, for a given item, which version was produced when that item was last changed (i.e. the item was created, modified or deleted) as far as this replica is aware, and the data showing the actual updated contents (not shown in Table 1). Thus, for example, replica A knows that the 7th change in replica C was to item j, and it includes the data associated with the change to item j.
Similarly, replica B has a data store 24 including a knowledge vector, KB, and a set of replicated items. The knowledge vector in replica B represents what knowledge replica B has about changes that have occurred to items in the collection. For example, knowledge vector KB may have the components:KB=A2B5C8.
This means that replica B has knowledge including changes up to the 2nd change in replica A, the 5th change in replica B and the 8th change in replica C. Each of these changes is represented in the set of items stored by replica B.
Referring now to prior art FIG. 3, at time 1, replica A sends a sync request along with replica A's knowledge, which may be represented by replica A's knowledge vector, to replica B. At time 2, replica B examines replica A's knowledge by comparing the respective knowledge vectors. Replica B discovers that replica A is not aware of changes made by replica B that are labeled with the version B5, or changes made by replica C (which are known to replica B) that are labeled with the version C8. Thus, replica B sends the items with these versions. Subsequently or simultaneously as illustrated in time 3, replica B sends to replica A replica B's learned knowledge.
As this is a one-way synchronization, this ends the sync process resulting from replica A's sync request (in a two way sync, the process would be repeated with replica B receiving changes from replica A and learning what knowledge replica A has). Replica A can update its knowledge vector based on the learned knowledge and received changes to include the recently replicated changes as shown in Replica A in FIG. 3.
Knowledge vectors impose substantially lower overhead compared to version vectors. The space required per replica to store knowledge vectors is just O(N+M), including the space required for per item version numbers, compared to O(N*M) for version vectors, where the system has N replicas and the replica has M items. Further more, exchanging knowledge vectors only requires O(N) bandwidth compared to O(N*M) for exchanging version vectors.
While knowledge vectors work well for total replication between replicas, it may happen that one or more replicas are only interested in receiving a certain subset of information. This situation is referred to as partial replication. For example, suppose the data store includes email messages in various folders, including an inbox folder and some number of other folders including, perhaps, folders that contain saved email messages. In some cases a user might want to replicate changes to all of the email folders. For example, this might be desirable when the communications bandwidth between replicating devices is large. In other cases—perhaps when the bandwidth is limited, as it might be at some times with a mobile phone or PDA—the user might only want to replicate changes to a particular folder, like their inbox.
It is also conceivable that a user might want to synchronize only part of their entire set of data in all cases. For example, a user might want to maintain all email on a desktop computer or server, but only synchronize their inbox and a selected set of folders to a small device that has limited storage. In this case, some information may never be synchronized with a particular device.
As another example, for a data store that includes digital music files, a user might want to synchronize their entire digital music library—perhaps they have a portable music player or computer with a large hard drive. They may also have a small portable music player with a limited amount of flash memory, on which they only want to store a selected set of music. In one example, this music to be synchronized might include, for example, digital music files the user has rated with “four stars” or “five stars,” as well as music downloaded in the last week.
In order to allow for partial replication in the above situations, as well as a wide variety of others, a replica may contain a filter. A “filter” may be broadly defined as any construct that serves to identify a particular set of items in a data collection. These items are said to fall within the partial replica's “interest set”. When synchronizing in a partial replication scenario, like in the situations introduced above, various additional problems may occur. These problems include the following:
Efficient knowledge sharing: A partial replica is interested in only a certain subset of items and consequently has knowledge that is limited by its interest set. When a partial replica shares its knowledge with a second replica, the second replica must somehow account for this limitation. This is not a problem for a version vector knowledge sharing scheme, which maintains knowledge about each item separately. However, a knowledge vector knowledge sharing scheme maintains its knowledge vector about the replica as a whole rather than about each item separately. This results in a substantial savings in storage and bandwidth as compared with version vectors, but it also makes it a problem to account for a limited interest set.
Partial information: In order for a replica to eventually learn about an item within its interest set, it requires a synchronization path to all other replicas that are interested in the same item. Moreover, each intermediate replica in the synchronization path must also be interested in the item. Otherwise, a replica may not receive complete information about all the items it is interested in. For example, in FIG. 1, if the camera F takes a picture that the cell phone D wants to use as a background but the laptop C and the PDA E are not interested in the picture then the cell phone D has no way of obtaining it with its existing synchronization topology and methods.
Push outs: When a partial replica updates an item, the updated item may no longer fall within the replica's interest set. Although the partial replica would like to discard such an item, it may find itself in the situation of holding the only copy, in which case discarding the updated item would cause the update to evaporate from the collection. In this situation, the partial replica must “push out” the item to another replica before discarding it. A similar situation can arise when a partial replica alters its filter. For example, in FIG. 1, while a user might take a large number of pictures with digital camera F, perhaps the user desires a policy of storing only the most recent 100 pictures on the camera because of its limited storage. Such a policy could be effected by altering the camera's filter each time a new picture is taken so as to exclude an old picture. However, camera F can safely discard the old picture only if there is a guarantee that the picture is stored elsewhere. This could be done by transferring the picture to another replica during synchronization. However, ensuring such transfers eventually result in durable storage for the pictures is difficult with arbitrary synchronization topologies.
Move outs: When a partial replica is the target of a synchronization, the source replica may be aware of an update to an item for which an old version is stored by the partial replica, but the new version does not fall within the partial replica's interest set. The partial replica needs to be made aware that the item it stores has been updated so as to “move out” of its interest set. For example, in FIG. 1, suppose that Laptop B stores a full calendar of all baseball games and cell phone D is interested in storing only weekend games. A weekend game moves to a week day and the user at Laptop B updates the item accordingly. When cell phone D next synchronizes from Laptop B, it must receive a “move-out” notification.
Reincarnation: When a replica deletes an item, the system needs to ensure that all copies of that item are permanently deleted from the system. If not, the deleted copy might get resurrected at a later point of time based on an old version. Resurrection of deleted items is a concern even without considering partial replicas. Partial replicas add the related problem that an item discarded due to a move-out might be “reincarnated” from an old version synced from an out-of-date replica.
Filter Changes: Finally, replicas may change filters at any time causing some items to move out of the interest set as well as disrupt the path of information flow the replica relies on to learn new items. For example, in FIG. 1, if the laptop C changes its filter to exclude all pictures then replicas A, B, and D may have no way of receiving the pictures taken by the camera F (assuming PDA E was not interested in pictures in the first place). It is desirable to ensure that filter changes do not disrupt information flow and items discarded during filter changes are completely expunged without the risk of resurrections.
Except for the problem of efficient knowledge sharing, a reason for the above problems is that arbitrary synchronization topologies do not provide a guaranteed path of information flow for replicas. A solution to provide guaranteed information paths is to have one or more replicas serve as reference replicas, which replicate all the items in the system, and have replicas synchronize with a reference replica periodically. However, it may not be always possible for all replicas to synchronize with reference replicas. Moreover, reference replicas may not be reachable at a dire time of need.